package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

/**
 * 基于线性探测式hash的无序符号表
 * put:
 * get:
 * 使用时务必保证散列表的使用率小于50%，不然效率会大大降低
 * 
 * @author 付大石
 */
public class LinearProbingHashST<K, V> {

    public static void main(String[] args) {

        LinearProbingHashST<Character, Integer> st = new LinearProbingHashST();
        st.put('S', 0);
        st.put('E', 1);
        st.put('A', 2);
        st.put('R', 3);
        st.put('C', 4);
        st.put('H', 5);
        st.put('E', 6);
        st.put('X', 7);
        st.put('A', 8);
        st.put('M', 9);
        st.put('P', 10);
        st.put('L', 11);
        st.put('E', 12);
        st.put('F', 12);
        st.put('G', 12);
        st.put('H', 12);
        for (Character item : st.keys()) {
            System.out.println(item + "   " + st.get(item));
        }
        System.out.println(st.size());
    }

    /**
     * 符号表初始大小
     */
    private static final int DEFAULT_CAPACITY = 512;

    /**
     * key数组
     */
    private K[] keyArr;

    /**
     * value数组
     */
    private V[] valueArr;

    /**
     * 可存储的键值对总数
     */
    private int m;

    /**
     * 已存储的键值对总数
     */
    private int n;

    public LinearProbingHashST() {
        this(DEFAULT_CAPACITY);
    }

    public LinearProbingHashST(int capacity) {
        keyArr = (K[]) new Object[capacity];
        valueArr = (V[]) new Object[capacity];
        m = capacity;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % m;
    }

    public void put(K key, V value) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (value == null) {
            delete(key);
            return;
        }
        if (n * 2 > m) {
            resize(m * 2);
        }
        int i = hash(key);
        for (; keyArr[i] != null; i = (i + 1) % m) {
            if (keyArr[i].equals(key)) { // 键值对已存在于符号表中
                valueArr[i] = value;
                return;
            }
        }
        keyArr[i] = key;
        valueArr[i] = value;
        n++;
    }

    private void resize(int newCapacity) {

        LinearProbingHashST<K, V> st = new LinearProbingHashST<>(newCapacity);
        for (int i = 0; i < keyArr.length; i++) {
            if (keyArr[i] != null) {
                st.put(keyArr[i], valueArr[i]);
            }
        }
        keyArr = st.keyArr;
        valueArr = st.valueArr;
        m = st.m;
    }

    public void delete(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (!contains(key)) {
            return;
        }
        int i = hash(key);
        System.out.println(keyArr[i]);
        System.out.println(key);
        while (!keyArr[i].equals(key)) {
            i = (i + 1) % m;
        }
        keyArr[i] = null;
        valueArr[i] = null;
        n--;
        i = (i + 1) % m;
        for (; keyArr[i] != null; i = (i + 1) % m) {
            K tempK = keyArr[i];
            V tempV = valueArr[i];
            keyArr[i] = null;
            valueArr[i] = null;
            n--;
            put(tempK, tempV);
        }
        if (m < DEFAULT_CAPACITY) {
            if (n * 8 < m) {
                resize(m / 2);
            }
        }

    }

    public V get(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        for (int i = hash(key); keyArr[i] != null; i = (i + 1) % m) {
            if (keyArr[i].equals(key)) {
                return valueArr[i];
            }
        }
        return null;
    }

    public int size() {
        return n;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public boolean contains(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        return get(key) != null;
    }

    public Iterable<K> keys() {

        List<K> list = new ArrayList<>();
        for (K key : keyArr) {
            if (key != null) {
                list.add(key);
            }
        }
        return list;
    }
}
